package com.leetcode.动态规划;

/**
 * 给定两个单词 word1 和 word2 ，返回使得 word1 和  word2 相同所需的最小步数。
 * 每步 可以'删除'任意一个字符串中的一个字符。(只能删除操作)
 * @author LZF
 *
 */
public class L583两个字符串的删除操作 {
	public static void main(String[] args) {
		int result = minDistance("sea","eat");
		System.out.println(result);
	}
	
	/**
	 * dp[i][j]:让w1[0,i]与w2[0,j]相同而删除的最小步骤。w1[0,i]表示w1下标0到i的字串
	 * 
	 * if(w1[i] == w2[j]) 则不用进行操作 dp[i][j]=dp[i-1][j-1]
	 * else 则需要进行删除操作
	 * 删除有三种情况：
	 * 1、删除w1[i]，占一个操作数，则还需要加上dp[i-1][j]
	 * 2、删除w2[j]，占一个操作数，则还需要加上dp[i][j-1]
	 * 3、删除w1[i]和w2[j]，占两个操作数，则还需要加上dp[i-1][j-1]
	 * dp[i][j]取三者的最小值
	 * 
	 * 初始化：
	 * if(w1[0] != w2[0]) 则dp[0][0]=2（删除w1[0]和w2[0]，使得两个成为空串相等）
	 * if(i > 1) dp[i][0] = (w1[i] == w2[0]) ? i : min(i+2,dp[i - 1][0] + 1)
	 * 解释：i：w1[i]和w2[0]不用删，w1的其他元素删，因为w2只有一个元素，最多最有一个元素相等，其他都是多余的
	 * 	(i+2):w1[i]和w2[0]不相等，则都删除，使得两个都为空串相等
	 * dp[i - 1][0]:删除w1[i]，占一个操作数，则还需要加上dp[i-1][0]
	 * 同理，if(j>1) dp[0][j] = (w1[0] == w2[j]) ? j: min(j + 2,dp[0][j-1]+1)
	 */
	public static int minDistance(String word1, String word2) {
		int[][] dp = new int[word1.length()][word2.length()];
		dp[0][0] = word1.charAt(0) == word2.charAt(0) ? 0 : 2;
		for(int i = 1;i < word1.length();i++)
			dp[i][0] = word1.charAt(i) == word2.charAt(0) ? i : Math.min(i + 2,dp[i - 1][0] + 1);
		for(int j = 1;j < word2.length();j++)
			dp[0][j] = word1.charAt(0) == word2.charAt(j) ? j : Math.min(j + 2,dp[0][j - 1] + 1);
		for(int i = 1;i < word1.length();i++) {
			for(int j = 1;j < word2.length();j++) {
				if(word1.charAt(i) == word2.charAt(j))
					dp[i][j] = dp[i - 1][j - 1];
				else
					dp[i][j] = Math.min(dp[i - 1][j - 1] + 2,Math.min(dp[i - 1][j] + 1,dp[i][j - 1] + 1));
			}
		}
		return dp[word1.length() - 1][word2.length() - 1];
    }
}
